package demo;

import java.util.List;

public class DpDemo {
    public static void main(String[] args) {

//        System.out.println(getDp(20));
//        System.out.println(recover(20));
//        List<Integer> integers = Arrays.asList(1, 2, 5);
//        System.out.println(getCoins(integers, 10));
//        System.out.println(getEdit("rad", "apple"));

//        int[] wt = {2, 1, 3};
//        int[] val = {4, 2, 3};
//        System.out.println(getWeight(4, 3, wt, val));
        System.out.println(getIncr(new int[]{10, 9, 2, 5, 8, 7, 101, 18}));
    }

    //动态规划 斐波那数组
    public static int getDp(int num) {

        int[] dp = new int[num + 1];

        dp[0] = 0;
        dp[1] = 1;
        //
        // dp[i] = { 1  n=1,2 }
        //         { dp[i-1]+dp[i-2] i>2}
        for (int i = 2; i <= num; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[num];
    }

    //递归
    public static int recover(int num) {
        if (num == 1 || num == 2) return 1;
        return recover(num - 2) + recover(num - 1);
    }

    //硬币 1 2 5   11
    //0 1 2 3 4 5 6 7 8
    //0 1 1 2 2 1 2 2 3
    public static int getCoins(List<Integer> coins, int amount) {
        //定义状态转移方程 dp[i] 是指 集成i钱 需要最少dp[i]个硬币。
        int[] dp = new int[amount + 1];

        if (amount == 0) return 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = i + 1;//默认给最大值
            for (int coin : coins) {
                if (i - coin < 0) {
                    continue;
                }
                //取交换
                dp[i] = Math.min(dp[i - coin] + 1, dp[i]);

            }
        }

        return dp[amount];
    }


    /**
     * 编辑问题
     */
    public static int getEdit(String s1, String s2) {
        int i1 = s1.length();
        int i2 = s2.length();
        //dp[i][j]定义如下 对于前s1[i]转换换成s2[j] 最少要编辑d[i][j]次。
        int[][] dp = new int[i1 + 1][i2 + 1];
        for (int i = 1; i <= i1; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= i2; j++) {
            dp[0][j] = j;
        }
        //动态规划
        for (int i = 1; i <= i1; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= i2; j++) {
                char c2 = s2.charAt(j - 1);
                if (c1 == c2) {
                    //跳过
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //插入 删除 替换
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[i1][i2];
    }

    /**
     * 给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
     * 例如: N = 3, W = 4
     * wt = [2, 1, 3]
     * val = [4, 2, 3]
     * 返回6
     * 0-1 背包问题
     * 不可分割
     * 状态 是背包的容量和可选择的物品
     */
    public static int getWeight(int packetSize, int count, int[] wt, int[] val) {
        int[][] dp = new int[count + 1][packetSize + 1];
//        dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。
//        for (int i = 0; i < count + 1; i++) {
//            dp[i][0] = 0;
//        }
//        for (int i = 0; i < packetSize + 1; i++) {
//            dp[0][i] = 0;
//        }

        for (int i = 1; i < count + 1; i++) {
            for (int w = 1; w < packetSize + 1; w++) {
                if (w - wt[i - 1] < 0) {
                    //容量装不下时,只能选择不装入背包
                    dp[i][w] = dp[i - 1][w];
                } else {
                    //装入或者不装入
                    dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w]);
                }
            }
        }

        return dp[count][packetSize];
    }

    /**
     * 购物车问题
     * 要买归类为附件的物品，必须先买该附件所属的主件 最多有1个附件
     * 例如: N = 3, W = 4
     * wt = [2, 1, 3]
     * val = [4, 2, 3]
     * 附件ex = [0,1,1]
     */

    public static int getOrders(int packetSize, int count, int[] wt, int[] val, int[] ex) {
        int[][] dp = new int[count + 1][packetSize + 1];

        for (int i = 1; i < count + 1; i++) {
            for (int w = 1; w < packetSize + 1; w++) {
                if (ex[i - 1] > 0) {
                    //是附件  必须在0-i-1之间找到主件
                    dp[i][w] = dp[i - 1][w];
                } else {
                    //如果是附件 先判断是否取到主件
                    //wt[ex[i-1]] 主件的重量
                    //val[ex[i-1]] 主件的价值
//                    w - wt[i-1] - wt[ex[i-1]] <0;
                    if (w - wt[i - 1] - wt[ex[i - 1]] < 0) {
                        //容量装不下时,只能选择不装入背包
                        dp[i][w] = dp[i - 1][w];
                    } else {
                        //装入或者不装入
                        dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1] - wt[ex[i - 1]]] + val[i - 1] + val[ex[i - 1]], dp[i - 1][w]);
                    }
                }

            }
        }

        return dp[count][packetSize];
    }


    //最长子序列

    //最长上升子序列
    //10 9 2 5 8 7 101 18
    //1  1 1 2 3 3  4  4
    public static int getIncr(int[] arr) {
        int[] dp = new int[arr.length];
        //表示arr[i]最长递增子序列长度是dp[i];
//        dp[0] = 1;
//        for (int i = 1; i < arr.length ; i++) {
//            if (arr[i] < arr[i - 1]) {
//                dp[i] = dp[i - 1];
//            } else {
//                dp[i] = dp[i-1] + 1;
//            }
//        }
        int result = 1;
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            result = Math.max(result, dp[i]);
        }

        return result;
    }
}
